import random
def generateRandomList(size):
	'''return a list, contains 'size' of random number
	'''
	list=[]
	while size>0:
		list.append(random.randint(1,99))
		size-=1
	return list

def test(result, expectation,type):
	'''test if the result equals expectation
	'''
	if result==expectation:
		print type,'OK, result:', result 
	else:
		print type,'Failed!!!\n', 'Expect: ', expectation, '\nBut got:', result
		
def exchange(a,i,j):
	'''swap element with index i and element with index j in the list a
	'''
	temp=a[i]
	a[i]=a[j]
	a[j]=temp

def shell_sort(list):
	'''Shell sort using Shell's (original) gap sequence: n/2, n/4, ..., 1.'''
	gap = len(list) / 2
	# loop over the gaps
	while gap > 0:
		# do the insertion sort
		efficency_insertion_sort(list,gap)
		gap /= 2
	return list
			
		
def insertion_sort(list):
	'''left to right for inner loop, need many reallocation
	'''
	i=0
	while i<len(list):
		j=0
		while j<i+1:
			if list[i]<list[j]:
				temp=list.pop(i)
				list.insert(j, temp)
				j=i+1 #break the look
			j+=1
		i+=1
	return list

def efficency_insertion_sort(list,gap=1):
	''' right to left for inner loop, much better than previous one
	takes linear time when input is already sorted'''
	for i in range(gap,len(list)):
		temp = list[i]
		while temp<list[i-gap] and i>0:
			list[i]=list[i-gap]
			i-=gap
		list[i]=temp
	return list

def selection_sort(list):
	''' always takes N^2 time no matter what the input is'''
	i=0
	while i<len(list):
		j=i
		index=i
		while j<len(list):
			if list[j]<list[index]:
				index=j
			j+=1
		exchange(list, index, i)
		i+=1
	return list






















def main():
	lenth=10
	list = generateRandomList(lenth)
	print 'Original: ', list,''
	test(selection_sort(list), sorted(list),'selection sort')
	list = generateRandomList(lenth)
	print 'Original: ', list,''
	test(insertion_sort(list), sorted(list),'insertion sort')
	list = generateRandomList(lenth)
	print 'Original: ', list,''
	test(efficency_insertion_sort(list), sorted(list),'efficency_insertion_sort')
	list = generateRandomList(lenth)
	print 'Original: ', list,''
	test(shell_sort(list), sorted(list),'shell_sort')
	
if __name__ == '__main__':
	main()
